{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Tree Postorder Traversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #depth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #深度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: postorderTraversal"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的后序遍历"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一棵二叉树的根节点 <code>root</code> ，返回其节点值的 <strong>后序遍历 </strong>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/08/28/pre1.jpg\" style=\"width: 127px; height: 200px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1,null,2,3]\n",
    "<strong>输出：</strong>[3,2,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = []\n",
    "<strong>输出：</strong>[]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>root = [1]\n",
    "<strong>输出：</strong>[1]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数目在范围 <code>[0, 100]</code> 内</li>\n",
    "\t<li><code>-100 &lt;= Node.val &lt;= 100</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>递归算法很简单，你可以通过迭代算法完成吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-tree-postorder-traversal](https://leetcode.cn/problems/binary-tree-postorder-traversal/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-tree-postorder-traversal](https://leetcode.cn/problems/binary-tree-postorder-traversal/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,null,2,3]', '[]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        ret = []\n",
    "        if root.left is not None:\n",
    "            ret.extend(self.postorderTraversal(root.left))\n",
    "        \n",
    "        if root.right is not None:\n",
    "            ret.extend(self.postorderTraversal(root.right))\n",
    "        ret.append(root.val)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        List = []\n",
    "        \n",
    "        def getResult(root):\n",
    "            if root == None:\n",
    "                return\n",
    "            if root.left != None:\n",
    "                getResult(root.left)\n",
    "            if root.right != None:\n",
    "                getResult(root.right)\n",
    "            List.append(root.val)\n",
    "        \n",
    "        getResult(root)\n",
    "        return List"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: 'TreeNode') -> 'List[int]':\n",
    "        \n",
    "        # using two stacks\n",
    "        # stack = [[], []]\n",
    "        # ret = []\n",
    "        # if root:\n",
    "        #     stack[0].append(root)\n",
    "        # while stack[0]:\n",
    "        #     node = stack[0].pop()\n",
    "        #     if node.left:\n",
    "        #         stack[0].append(node.left)\n",
    "        #     if node.right:\n",
    "        #         stack[0].append(node.right)\n",
    "        #     stack[1].append(node)\n",
    "        # while stack[1]:\n",
    "        #     node = stack[1].pop()\n",
    "        #     ret.append(node.val)\n",
    "        # return ret\n",
    "        \n",
    "        # using one stack\n",
    "        stack, ret = [], []\n",
    "        last = None\n",
    "        if root:\n",
    "            stack.append(root)\n",
    "            node = root.left\n",
    "        while stack:\n",
    "            if node:\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            else:\n",
    "                node = stack[-1]\n",
    "                if node.right and last != node.right:\n",
    "                    node = node.right\n",
    "                else:\n",
    "                    node = stack.pop()\n",
    "                    # processing\n",
    "                    ret.append(node.val)\n",
    "                    last = node\n",
    "                    node = None\n",
    "                \n",
    "        return ret\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "from queue import deque\n",
    "#前序遍历，用栈储存顺序，后迭代出栈。返回逆序结果\n",
    "class Solution():\n",
    "    def postorderTraversal(self, root):\n",
    "        if root is None:return []\n",
    "        q = deque()\n",
    "        q.append(root)\n",
    "        ret = []\n",
    "        while q:\n",
    "            nd = q.pop()\n",
    "            if nd.left:\n",
    "                q.append(nd.left)\n",
    "            if nd.right:\n",
    "                q.append(nd.right)\n",
    "            ret.append(nd.val)\n",
    "        return ret[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "\n",
    "        p = root\n",
    "        stack = []\n",
    "        last = None\n",
    "        res = []\n",
    "        while True:\n",
    "            while p:\n",
    "                stack.append(p)\n",
    "                p = p.left\n",
    "            if not stack:\n",
    "                break\n",
    "            top = stack[len(stack)-1]\n",
    "            if top.right == None or last == top.right:\n",
    "                stack.pop(len(stack)-1)\n",
    "                res.append(top.val)\n",
    "                last = top\n",
    "                p = None\n",
    "            else:\n",
    "                p = top.right\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        las = None\n",
    "        res = []\n",
    "        stack = []\n",
    "        while root!=None or len(stack)!=0:\n",
    "            if root!=None:\n",
    "                stack.append(root)\n",
    "                root = root.left          \n",
    "            else:\n",
    "                root = stack[-1]\n",
    "                if root.right!=None and root.right!=las:\n",
    "                    root = root.right\n",
    "                    stack.append(root)\n",
    "                    root = root.left\n",
    "                else:\n",
    "                    root = stack.pop()\n",
    "                    res.append(root.val)\n",
    "                    las = root\n",
    "                    root = None\n",
    "                \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        if not root: return []\n",
    "\n",
    "        output = []\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            node = stack.pop() \n",
    "            output.append(node.val)\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "        return output[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: 'TreeNode') -> 'List[int]':\n",
    "        if not root:\n",
    "            return []\n",
    "        \n",
    "        stack, res = [root], list()\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node.left:\n",
    "                stack.append(node.left)\n",
    "            if node.right:\n",
    "                stack.append(node.right)\n",
    "            res.insert(0, node.val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        if root is None:\n",
    "            return []\n",
    "        stack, output = [root, ], []\n",
    "        while stack:\n",
    "            root = stack.pop()\n",
    "            output.append(root.val)\n",
    "            if root.left is not None:\n",
    "                stack.append(root.left)\n",
    "            if root.right is not None:\n",
    "                stack.append(root.right)\n",
    "        \n",
    "        return output[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        stack = []\n",
    "        node = root\n",
    "        result = []\n",
    "        while node is not None or len(stack) > 0:\n",
    "            \n",
    "            while node is not None:\n",
    "                result.append(node.val)\n",
    "                stack.append(node)\n",
    "                node = node.right\n",
    "\n",
    "            node = stack.pop()\n",
    "\n",
    "            node = node.left\n",
    "            \n",
    "        result.reverse()\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        stack=[]\n",
    "        res=[]\n",
    "        p=root\n",
    "        while p or stack:\n",
    "            if p:\n",
    "                res.append(p.val)\n",
    "                stack.append(p.left)\n",
    "                p=p.right\n",
    "            else:\n",
    "                p=stack.pop()\n",
    "        return res[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.left = None\r\n",
    "#         self.right = None\r\n",
    "\r\n",
    "from typing import List\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def postorderTraversal(self, root: TreeNode) -> List[int]:\r\n",
    "        res = []\r\n",
    "        self.backward(root, res)\r\n",
    "        return res\r\n",
    "\r\n",
    "    def backward(self, node, res):\r\n",
    "        if not node:\r\n",
    "            return\r\n",
    "        self.backward(node.left, res)\r\n",
    "        self.backward(node.right, res)\r\n",
    "        res.append(node.val)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        node = root\n",
    "        r = []\n",
    "        stack = [(root, False)]\n",
    "        while stack:\n",
    "            node, is_expand = stack.pop()\n",
    "            if node and not is_expand:\n",
    "                stack.append((node, True))\n",
    "                stack.append((node.right, False))\n",
    "                stack.append((node.left, False))\n",
    "            elif node:\n",
    "                r.append(node.val)\n",
    "        return r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        res = list()\n",
    "        st = []\n",
    "        curNode = root\n",
    "        while st or curNode:\n",
    "            while curNode:\n",
    "                res.append(curNode.val)\n",
    "                st.append(curNode.left)\n",
    "                curNode = curNode.right\n",
    "            curNode = st.pop()\n",
    "        res.reverse()\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        if not root: return []\n",
    "\n",
    "        stack = []\n",
    "        result = []\n",
    "        stack.append((0, root))\n",
    "        \n",
    "        while stack:\n",
    "            op, node = stack.pop()\n",
    "            if not node:\n",
    "                continue\n",
    "            if op == 1:\n",
    "                result.append(node.val)\n",
    "            else:\n",
    "                stack.append((1, node))\n",
    "                stack.append((0, node.right))\n",
    "                stack.append((0, node.left))\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "            res = list()\n",
    "            st = []\n",
    "            st.append(root)\n",
    "            while st:\n",
    "                curNode = st.pop()\n",
    "                if curNode: res.append(curNode.val)\n",
    "                else: continue\n",
    "                st.append(curNode.left)\n",
    "                st.append(curNode.right)\n",
    "            res.reverse()\n",
    "            return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# https://www.pythonf.cn/read/142572\n",
    "\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        res = []  # 储存遍历结果\n",
    "        stack = []  # 模拟栈\n",
    "        if root:\n",
    "            stack.append(root)  # 根结点进栈保证循环正常进行，同时可以处理空树\n",
    "\n",
    "        while stack:\n",
    "            print(stack)\n",
    "            node = stack.pop()\n",
    "       \n",
    "            if node:\n",
    "                stack.append(node) # 顺着访问，因此逆着压栈，后序遍历是左右根，就先进根\n",
    "                stack.append(None) # None用来表示下个节点从栈里弹出来已经是第二次访问了\n",
    "                if node.right:\n",
    "                    stack.append(node.right) # 保证非空进栈\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "            else: #在第二次访问的时候，弹栈，对弹出的元素进行处理\n",
    "                res.append(stack.pop().val)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "# https://www.pythonf.cn/read/142572\n",
    "\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "        res = []  # 储存遍历结果\n",
    "        stack = []  # 模拟栈\n",
    "        if root:\n",
    "            stack.append(root)  # 根结点进栈保证循环正常进行，同时可以处理空树\n",
    "\n",
    "        while stack:\n",
    "            print(stack)\n",
    "            node = stack.pop()\n",
    "            if node:\n",
    "                # 左右根-》根右左\n",
    "                stack.append(node) # 顺着访问，因此逆着压栈，后序遍历是左右根，就先进根\n",
    "                stack.append(None) # None用来表示下个节点从栈里弹出来已经是第二次访问了\n",
    "                if node.right:\n",
    "                    stack.append(node.right) # 保证非空进栈\n",
    "                if node.left:\n",
    "                    stack.append(node.left)\n",
    "            else: #在第二次访问的时候，弹栈，对弹出的元素进行处理\n",
    "                res.append(stack.pop().val)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import os, sys, shutil, glob, re\n",
    "import time, calendar\n",
    "from datetime import datetime, timezone\n",
    "import hashlib, zipfile, zlib\n",
    "from math import *\n",
    "from operator import itemgetter\n",
    "from functools import wraps, cmp_to_key\n",
    "from itertools import count, combinations, permutations\n",
    "from collections import namedtuple, defaultdict, Counter\n",
    "from queue import Queue\n",
    "\n",
    "\n",
    "def postorderTraversal(node, func):\n",
    "  if not node:\n",
    "    return\n",
    "  postorderTraversal(node.left, func)\n",
    "  postorderTraversal(node.right, func)\n",
    "  func(node)\n",
    "\n",
    "class Solution:\n",
    "  def postorderTraversal(self, root):\n",
    "    res = []\n",
    "    postorderTraversal(root, lambda nd: res.append(nd.val))\n",
    "    return res\n",
    "\n",
    "\n",
    "if __name__ == '__main__' and ('SJDEAK' in os.environ):\n",
    "  from utils.tree import TreeNode, array2TreeNode\n",
    "\n",
    "\n",
    "  def test(*args):\n",
    "    print('输入数据: ', *args)\n",
    "    print('结果: ', Solution().postorderTraversal(*args), end='\\n-----\\n')\n",
    "\n",
    "  test(array2TreeNode([1,None,2,3]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: TreeNode) -> List[int]:\n",
    "\n",
    "        def postorder(root: TreeNode):\n",
    "            if not root:\n",
    "                return\n",
    "            postorder(root.left)\n",
    "            postorder(root.right)\n",
    "            res.append(root.val)\n",
    "        \n",
    "        res = []\n",
    "        postorder(root)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root):\n",
    "        a = []\n",
    "        if not root:return []\n",
    "        stack = [root]\n",
    "        while(stack):\n",
    "            node = stack.pop()\n",
    "            a.append(node.val)\n",
    "            if(node.left):\n",
    "                stack.append(node.left)\n",
    "            if(node.right):\n",
    "                stack.append(node.right)\n",
    "        return a[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def f(root,res):\n",
    "            if not root:\n",
    "                return\n",
    "            f(root.left,res)\n",
    "            f(root.right,res)\n",
    "            res.append(root.val)\n",
    "        res=[]\n",
    "        f(root,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "\"\"\"\n",
    "while cur \n",
    "    1. 无左树：cur = cur.right\n",
    "    2. 有左树，找到MR\n",
    "        MR.r == None: MR.r = cur,  cur = cur.left\n",
    "        MR.r == cur:  MR.r = None, cur = cur.right\n",
    "# 同时确保能一定找到MR.r在第二个while循环♻️中确认\n",
    "\n",
    "Preorder: 用else找到仅走一次的点 + 2.1首次出现第二次节点的情况\n",
    "Inorder: 当cur = cur.right的时候，打印（包含1.的情况+2.2第二次出现二次节点的情况） \n",
    "Postorder：找到出现两次点，然后打印左树；+ 对整个树的右边界用翻转链表逆序打印\n",
    "- 操作在2.2 print(cur.left)左树右边界\n",
    "- 操作在大while后，打印整颗树的右边界\n",
    "\"\"\"\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        def printEdge(head):\n",
    "            def reverseEdge(head):\n",
    "                pre = nxt = None\n",
    "                while head: # 存，z，移，移\n",
    "                    nxt = head.right\n",
    "                    head.right = pre # \n",
    "                    pre = head\n",
    "                    head = nxt\n",
    "                return pre\n",
    "            tail = reverseEdge(head)\n",
    "            cur = tail\n",
    "            while cur:\n",
    "                # nonlocal ans\n",
    "                ans.append(cur.val)\n",
    "                cur = cur.right\n",
    "            reverseEdge(tail)\n",
    "\n",
    "        cur = root\n",
    "        ans = []\n",
    "        while cur:\n",
    "            MR = cur.left\n",
    "            if MR:\n",
    "                while MR.right and MR.right != cur:\n",
    "                    MR = MR.right\n",
    "                if MR.right == None:\n",
    "                    MR.right = cur\n",
    "                    cur = cur.left\n",
    "                    continue\n",
    "                else: \n",
    "                    MR.right = None\n",
    "                    printEdge(cur.left)\n",
    "            cur = cur.right\n",
    "        printEdge(root)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "        # ans = []\n",
    "        # h = root\n",
    "        # if h is not None:\n",
    "        #     stack = [h]\n",
    "        #     c = None\n",
    "        #     tiaojian = -1\n",
    "        #     while stack:\n",
    "                # print(\"c:\",c.val if c else None,\" \",\"h:\",h.val if h else None,\" stack:\",[x.val for x in stack], \"  tiaojian:\", tiaojian, \" ans:\",ans,sep=\"\")\n",
    "        #         c = stack[-1]\n",
    "        #         if c.left is not None and h is not c.left and h is not c.right:\n",
    "        #             stack.append(c.left)\n",
    "        #             tiaojian = 1\n",
    "        #         elif c.right is not None and h is not c.right:\n",
    "        #             stack.append(c.right)\n",
    "        #             tiaojian = 2\n",
    "        #         else:\n",
    "        #             # print(\"c:\",c.val if c else None,\" \",\"h:\",h.val if h else None, sep=\"\")\n",
    "        #             cur = stack.pop().val\n",
    "        #             ans.append(cur)\n",
    "        #             h = c\n",
    "        #             tiaojian = 3\n",
    "        # return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "class TreeNode:\r\n",
    "    def __init__(\r\n",
    "        self, val: int = 0, left: TreeNode | None = None, right: TreeNode | None = None\r\n",
    "    ) -> None:\r\n",
    "        self.val = val\r\n",
    "        self.left = left\r\n",
    "        self.right = right\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def postorderTraversal(self, root: TreeNode | None) -> list[int]:\r\n",
    "        output: list[int] = []\r\n",
    "\r\n",
    "        def traversal(cur: TreeNode | None) -> None:\r\n",
    "            if cur is None:\r\n",
    "                return\r\n",
    "\r\n",
    "            traversal(cur.left)\r\n",
    "            traversal(cur.right)\r\n",
    "            output.append(cur.val)\r\n",
    "\r\n",
    "        traversal(root)\r\n",
    "        return output\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        write, grey = 1, 0\n",
    "        steak = []\n",
    "        res = []\n",
    "        steak.append((write, root))\n",
    "        while steak:\n",
    "            print(steak)\n",
    "            color, node = steak.pop()\n",
    "            if not node:\n",
    "                continue\n",
    "            if color == write:\n",
    "                steak.append((grey, node))\n",
    "                steak.append((write, node.right))\n",
    "                steak.append((write, node.left))\n",
    "            else:\n",
    "                res.append(node.val)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        resutl = []\n",
    "        stack = []\n",
    "        \n",
    "        if root != None:\n",
    "            stack.append(root)\n",
    "        while stack:\n",
    "            node = stack.pop()\n",
    "            if node != None:\n",
    "                stack.append(node)\n",
    "                stack.append(None)\n",
    "                if node.right != None:\n",
    "                    stack.append(node.right)\n",
    "                if node.left != None:\n",
    "                    stack.append(node.left)\n",
    "            else:\n",
    "                node = stack.pop()\n",
    "                resutl.append(node.val)\n",
    "        return resutl\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        ans, stk = [], []\n",
    "        node = root\n",
    "        r = None\n",
    "        while node or stk:\n",
    "            if node :\n",
    "                stk.append(node)\n",
    "                node = node.left\n",
    "            else :\n",
    "                node = stk[-1]\n",
    "                if node.right and node.right != r:\n",
    "                    node = node.right\n",
    "                else :\n",
    "                    stk.pop()\n",
    "                    ans.append(node.val)\n",
    "                    r = node\n",
    "                    node = None\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:\n",
    "        res = []\n",
    "        if root is None:return res\n",
    "        stack = collections.deque()\n",
    "        node = root\n",
    "        prev = None\n",
    "        while stack or node:\n",
    "            while node:\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            node = stack.pop()\n",
    "            if node.right is None or prev==node.right:\n",
    "                res.append(node.val)\n",
    "                prev = node\n",
    "                node = None\n",
    "            else:\n",
    "                stack.append(node)\n",
    "                node = node.right\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
